package org.cllib.ds;

import java.util.Comparator;

public class BinarySortTree {
	Comparator c;
	Node root;
	int count;
	public BinarySortTree(Comparator c){
		this.c = c;
	}
	
	public Node insert(Object o){
		Node node = null;
		if(root == null){
			root = new Node();
			root.setData(o);
			
			node = root;
		}else{
			Node n = root;
			Node pn = null;
			int r = 0;
			while(n != null){
				pn = n;
				Object no = n.getData();
				r = c.compare(o, no);
				if(r < 0){
					//move to left
					n = n.getLeft();
				}else {
					//move to right
					n = n.getRight();
				}
			}
			
			assert(pn != null);
			node = new Node();
			node.data = o;
			node.setParent(pn);
			
			
			if(r < 0){
				pn.setLeft(node);
			}else{
				pn.setRight(node);
			}
			node = pn;
		}
		
		count ++;
		
		return node;
	}
	
	public Node remove(Object o){
		Node node = find(o);
		
		if(node != null){
			if(node.getParent() == null){
				assert(node == root);
				root = null;
			}else{
				Node rn = null;
				Node ln = node.getLeft();
				while((rn = node.getRight()) != null){
				}
				
				if(rn == null){
					if(ln != null){
						ln.setParent(node.getParent());
						node.getParent().setLeft(rn);
					}
				}else{
					rn.getParent().setRight(null);
					
					rn.setLeft(ln);
					rn.setRight(node.getRight());
					rn.setParent(node.getParent());
					
					if(node.getParent().getLeft() == node){
						node.getParent().setLeft(rn);
					}else if(node.getParent().getRight() == node){
						node.getParent().setRight(rn);
					}else{
						throw new IllegalStateException();
					}
				}
			}
			
			count --;
		}
		
		return node;
	}
	
	public Node find(Object o){
		Node n = root;
		
		while(n != null){
			Object no = n.getData();
			int r = c.compare(o, no);
			if(r == 0){
				return n;
			}
			if(r < 0){
				//move to left
				n = n.getLeft();
			}else {
				//move to right
				n = n.getRight();
			}
		}
		return null;
	}
	
	public void clear(){
		root = null;
		count = 0;
	}
	
	public int size(){
		return count;
	}
	
	public boolean isEmpty(){
		return root != null;
	}
	
	public Object extract(){
		if(isEmpty()){
			return null;
		}
		
		Object o = root.data;
		
		remove(o);
		
		return o;
	}
}
